/**
*	@file AffectsBip.cpp
*
*	@brief this header file is to implement Affect table
*
*	@author zhou nan
*
*	@date 4/04/2012
*/

#include "AffectsBip.h"

vector<AssignSet>	AffectsBip::affectsbip_table_;
vector<AssignSet>	AffectsBip::affectsbip_table_t_;
AssignSet AffectsBip::affectsbip_has_a0_;
AssignSet AffectsBip::affectsbip_has_0a_;
AssignSet AffectsBip::affectsbip_has_a0_cache_;
AssignSet AffectsBip::affectsbip_has_0a_cache_;
bool	AffectsBip::affectsbip_has_00_;
bool	AffectsBip::affectsbip_has_00_cache_;


vector<AssignSet>	AffectsBip::affectsbip_star_table_;
AssignSet	AffectsBip::affectsbip_star_table_cache_;


struct WhileEntry1{
	BlkIdx while_blknode;
	bool ischanged;
};
struct FrontierStackEntry1{
	BlkIdx frontier;
	list<BlkIdx> call_stack;
	list<WhileEntry1*> while_entry;	
	VarSet affects_vars;
};
struct CallerProcEntry{
	ProcIdx caller_proc;
	VarSet affects_var;
};
struct WhileEntry{
	BlkIdx while_blknode;
	VarSet affects_var;
};
struct FrontierStackEntry{
	BlkIdx frontier;
	list<BlkIdx> call_stack;
	list<WhileEntry*> while_entry;	
	VarSet affects_vars;
};
struct PathUnitEntry{
	BlkIdx	frontier;
	list<BlkIdx> call_stack;
	list<BlkIdx> while_entry;
	VarSet affects_var;
};

//should I clear it?
typedef set<PathUnitEntry*> PathUnitSet;

void AffectsBip::RebuildAffectsBip()
{
	affectsbip_table_.resize(StmtTable::GetSizeAssign());
	affectsbip_table_t_.resize(StmtTable::GetSizeAssign());
	affectsbip_star_table_.resize(StmtTable::GetSizeAssign());
	for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
	{
		affectsbip_table_[i].resize(StmtTable::GetSizeAssign());
		affectsbip_table_t_[i].resize(StmtTable::GetSizeAssign());
		affectsbip_star_table_[i].resize(StmtTable::GetSizeAssign());
	}
	affectsbip_has_a0_.resize(StmtTable::GetSizeAssign());
	affectsbip_has_0a_.resize(StmtTable::GetSizeAssign());
	affectsbip_has_a0_cache_.resize(StmtTable::GetSizeAssign());
	affectsbip_has_0a_cache_.resize(StmtTable::GetSizeAssign());
	affectsbip_star_table_cache_.resize(StmtTable::GetSizeAssign());

	affectsbip_has_00_ = false;
	affectsbip_has_00_cache_ = false;
}

static void ComputeCallerRight(stack<FrontierStackEntry*>& call_path, ProcIdx procidx, FrontierStackEntry* current_frontier_entry)
{
	int j = StmtTable::GetSizeCall();

	for (int i=0; i<StmtTable::GetSizeCall();i++)
	{
		if (StmtTable::GetCallTNode(i+1)->value == procidx)
		{
			if (StmtTable::GetCallGNode(i+1)->next_a != NULL)
			{
				FrontierStackEntry* frontier_entry = new FrontierStackEntry();
				frontier_entry->affects_vars = current_frontier_entry->affects_vars;
				frontier_entry->frontier = StmtTable::GetStmtBlkNode(StmtTable::GetCallGNode(i+1)->next_a->stmt_num)->blk_idx;
				call_path.push(frontier_entry);
			}
			else
			{	
				ComputeCallerRight(call_path, StmtTable::GetProcIdx(StmtTable::GetCallGNode(i+1)->stmt_num), current_frontier_entry);
			}
		}
	}
}

static void ComputeCallerRight(stack<FrontierStackEntry1*>& call_path, ProcIdx procidx, FrontierStackEntry1* current_frontier_entry)
{
	int j = StmtTable::GetSizeCall();

	for (int i=0; i<StmtTable::GetSizeCall();i++)
	{
		if (StmtTable::GetCallTNode(i+1)->value == procidx)
		{
			if (StmtTable::GetCallGNode(i+1)->next_a != NULL)
			{
				FrontierStackEntry1* frontier_entry = new FrontierStackEntry1();
				frontier_entry->affects_vars = current_frontier_entry->affects_vars;
				frontier_entry->frontier = StmtTable::GetStmtBlkNode(StmtTable::GetCallGNode(i+1)->next_a->stmt_num)->blk_idx;
				call_path.push(frontier_entry);
			}
			else
			{	
				ComputeCallerRight(call_path, StmtTable::GetProcIdx(StmtTable::GetCallGNode(i+1)->stmt_num), current_frontier_entry);
			}
		}
	}
}

static void AddFrontier(stack<FrontierStackEntry*>& call_path, BlkIdx frontier,FrontierStackEntry* frontier_entry,list<WhileEntry*>& while_entry_list_temp )
{
	FrontierStackEntry* p_frontier_stack_entry_new = new FrontierStackEntry();
	p_frontier_stack_entry_new->frontier=frontier;
	p_frontier_stack_entry_new->call_stack = frontier_entry->call_stack;


	p_frontier_stack_entry_new->while_entry = while_entry_list_temp;
	p_frontier_stack_entry_new->affects_vars = frontier_entry->affects_vars;
	call_path.push(p_frontier_stack_entry_new);
}

static void AddFrontier(stack<FrontierStackEntry1*>& call_path, BlkIdx frontier,FrontierStackEntry1* frontier_entry)
{
	FrontierStackEntry1* p_frontier_stack_entry_new = new FrontierStackEntry1();
	p_frontier_stack_entry_new->frontier=frontier;
	p_frontier_stack_entry_new->call_stack = frontier_entry->call_stack;


	p_frontier_stack_entry_new->while_entry = frontier_entry->while_entry;
	p_frontier_stack_entry_new->affects_vars = frontier_entry->affects_vars;
	call_path.push(p_frontier_stack_entry_new);
}

static void UpdateAffectsVarsForAssignBlkNode(VarSet& affects_vars, BlkIdx blkidx, AssignSet& result)
{
	//may need a flag
	bool affected = false;
	VarSet used_var,modifies_varset;
	for(int i=BlkTable::GetBlkNode(blkidx)->stmt_num_start;i<=BlkTable::GetBlkNode(blkidx)->stmt_num_end;i++)
	{
		int modifies_var;
		modifies_varset =Modifies::GetModifiesS(i);  
		used_var = Uses::GetUsesS(i);
		for(int m=0; m<VarTable::GetSize(); m++)
		{
			if(modifies_varset[m]==true) {modifies_var = m+1; break;}
		}
		for (int a=0;a<VarTable::GetSize();a++) //loop affects_var
		{
			//used a affected variable
			if(affects_vars[a]==true  && used_var[a]==true)
			{
				result[StmtTable::GetStmtTNode(i)->value-1] = true;
				affects_vars[modifies_var-1] = true; 
				affected=true;
				break;
			}
		}
		if(!affected) {affects_vars[modifies_var-1]= false;}
	}
}

AssignSet& AffectsBip::GetAffectsBipRight(AssignNum assign_num_left)
{
	stack<FrontierStackEntry1*> call_path;
	VarIdx original_modifies = StmtTable::GetAssignTNode(assign_num_left)->child->value;
	AssignSet result(StmtTable::GetSizeAssign(), false);

	//if cached, return result
	if( affectsbip_has_a0_cache_[assign_num_left - 1] )
		return affectsbip_table_[assign_num_left - 1];

	//Traverse through current blknode
	for( StmtNum i = StmtTable::GetAssignTNode(assign_num_left)->stmt_num + 1;
		i <= StmtTable::GetStmtBlkNode(StmtTable::GetAssignTNode(assign_num_left)->stmt_num)->stmt_num_end; 
		i++ )
	{
		if(  Uses::IsUsesS(i, original_modifies) )
		{
			result[StmtTable::GetStmtTNode(i)->value - 1] = true;
		}
		if( Modifies::IsModifiesS(i, original_modifies))
		{
			original_modifies = 0;
			break;
		}
	}
	BlkSet current_frontiers = BlkTable::GetNextBlkRight(StmtTable::GetStmtBlkNode(StmtTable::GetAssignTNode(assign_num_left)->stmt_num)->blk_idx);
	//push frontier blknode into stack_frontier.
	if (original_modifies != 0)
	{
		for( int i = 0; i < BlkTable::GetSize(); i++ )
		{
			if( current_frontiers[i])
			{
				FrontierStackEntry1* p_frontier_stack_entry_new = new FrontierStackEntry1();
				p_frontier_stack_entry_new->frontier=i+1;
				p_frontier_stack_entry_new->affects_vars.resize(VarTable::GetSize());
				p_frontier_stack_entry_new->affects_vars[original_modifies-1] = true;
				call_path.push(p_frontier_stack_entry_new);
			}
		}
	}
	if (call_path.empty()&&original_modifies!=0)
	{
		//***
		FrontierStackEntry1* p_frontier_stack_entry_new = new FrontierStackEntry1();
		p_frontier_stack_entry_new->affects_vars.resize(VarTable::GetSize());
		p_frontier_stack_entry_new->affects_vars[original_modifies-1] = true;
		ComputeCallerRight(call_path,StmtTable::GetProcIdx(StmtTable::GetAssignTNode(assign_num_left)->stmt_num), p_frontier_stack_entry_new);
	}

	while(!call_path.empty())
	{
		if (BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == ASSIGN_TYPE)	
		{
			if (call_path.top()->affects_vars[original_modifies-1] == true)
			{
				for (int i=0; 
					i< BlkTable::GetBlkNode(call_path.top()->frontier)->use_bef_mod[original_modifies-1].size();
					i++)
				{
					result [StmtTable::GetStmtTNode(BlkTable::GetBlkNode(call_path.top()->frontier)->use_bef_mod[original_modifies-1][i])->value-1] = true;
				}
			}
			//If var is affected, stop the path
			if (BlkTable::GetBlkNode(call_path.top()->frontier)->last_mod[original_modifies-1] != 0)
			{
				call_path.pop();
				//call_path.top()->affects_vars[original_modifies-1] = false;
			}
			else if (BlkTable::GetBlkNode(call_path.top()->frontier)->next_a != NULL)
			{
				//push new frontiers
				FrontierStackEntry1* frontier_entry = call_path.top();
				call_path.pop();
				AddFrontier(call_path, BlkTable::GetBlkNode(frontier_entry->frontier)->next_a->blk_idx,frontier_entry);
			}
			//end of proc
			else 
			{
				list<BlkIdx> call_stack_temp=call_path.top()->call_stack;
				if (!call_path.top()->call_stack.empty())
				{
					FrontierStackEntry1* frontier_entry = call_path.top();
					while (!frontier_entry->call_stack.empty()&& BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a ==NULL)
					{
						call_stack_temp=call_path.top()->call_stack;
						frontier_entry->call_stack.pop_back();
					}
					frontier_entry->call_stack=call_path.top()->call_stack;	
					//modify call_stack and while_stack
					frontier_entry->while_entry=call_path.top()->while_entry;
					call_path.pop();
					if(!frontier_entry->call_stack.empty())
					{AddFrontier(call_path, BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a->blk_idx,frontier_entry);
					call_path.top()->call_stack.pop_back();}
					else{}
				}
				else{
					FrontierStackEntry1* frontier_entry = call_path.top();	
					call_path.pop();
					ComputeCallerRight(call_path,StmtTable::GetProcIdx(BlkTable::GetBlkNode(frontier_entry->frontier)->stmt_num_start), frontier_entry);
				}
			}

		}

		else if(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == WHILE_TYPE )
		{
			//first time reach a while statement.
			if (call_path.top()->while_entry.size() ==0 || call_path.top()->while_entry.back()->while_blknode != BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx)
			{
				FrontierStackEntry1* frontier_entry = call_path.top();
				FrontierStackEntry1* frontier_entry_b = call_path.top();
				//add next_a
				WhileEntry1* while_entry=new WhileEntry1();
				while_entry->ischanged=false;
				while_entry->while_blknode = BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx;
				frontier_entry->while_entry.push_back(while_entry);
				call_path.pop();
				BlkIdx while_next_stmt_a = BlkTable::GetBlkNode(frontier_entry->frontier)->next_a->blk_idx;
				AddFrontier(call_path, while_next_stmt_a,frontier_entry);
				//add next_b
				if (BlkTable::GetBlkNode(frontier_entry->frontier)->next_b != NULL)
				{
					BlkIdx while_next_stmt_a = BlkTable::GetBlkNode(frontier_entry->frontier)->next_b->blk_idx;
					frontier_entry->while_entry.pop_back();
					AddFrontier(call_path, while_next_stmt_a,frontier_entry);
				}
				else
				{
					if(!call_path.top()->call_stack.empty())
					{
						while (!call_path.top()->call_stack.empty()&&BlkTable::GetBlkNode(call_path.top()->call_stack.back())->next_a ==NULL)
						{
							call_path.top()->call_stack.pop_back();
						}
						if(!call_path.top()->call_stack.empty())
						{
							frontier_entry_b->call_stack=call_path.top()->call_stack;
							//modify call_stack and while_stack
							frontier_entry_b->call_stack.pop_back();
							frontier_entry_b->while_entry.pop_back();
							AddFrontier(call_path, BlkTable::GetBlkNode(call_path.top()->call_stack.back())->next_a->blk_idx,frontier_entry_b);
						}
						else{}
					}
					else
					{
						list<FrontierStackEntry1*> frontier_entry_temp;
						ComputeCallerRight(call_path,StmtTable::GetProcIdx(BlkTable::GetBlkNode(call_path.top()->frontier)->stmt_num_start), call_path.top());
					}
				}
			}
			//X time reach a while statement.
			else {
				if(call_path.top()->while_entry.back()->ischanged == true)
				{
					call_path.top()->while_entry.back()->ischanged = false;
				}
				call_path.pop();
			}	
		}

		else if(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == CALL_TYPE )
		{
			//real call next blkNode
			StmtNum call_stmt_next = ProcTable::GetStmtNumStart(StmtTable::GetStmtTNode(BlkTable::GetBlkNode(call_path.top()->frontier)->stmt_num_start)->value);
			BlkNode* call_blk_next = StmtTable::GetStmtBlkNode(ProcTable::GetStmtNumStart(StmtTable::GetStmtTNode(BlkTable::GetBlkNode(call_path.top()->frontier)->stmt_num_start)->value));
			//add new element into call_path
			FrontierStackEntry1* p_frontier_stack_entry_new = new FrontierStackEntry1();
			p_frontier_stack_entry_new->frontier=call_blk_next->blk_idx;
			p_frontier_stack_entry_new->call_stack=call_path.top()->call_stack;
			p_frontier_stack_entry_new->call_stack.push_back(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx);
			p_frontier_stack_entry_new->while_entry=call_path.top()->while_entry;
			p_frontier_stack_entry_new->affects_vars = call_path.top()->affects_vars;
			call_path.pop();
			call_path.push(p_frontier_stack_entry_new);
		}
		//If statement always has next_a
		else
		{
			//push new frontiers
			current_frontiers = BlkTable::GetNextBlkRight(call_path.top()->frontier);
			FrontierStackEntry1* frontier_entry = call_path.top();
			call_path.pop();
			for( int i = 0; i < BlkTable::GetSize(); i++ )
			{
				if( current_frontiers[i] )
				{
					AddFrontier(call_path,i+1,frontier_entry);
				}
			}
		}
	}
	affectsbip_table_[assign_num_left - 1] = result;
	affectsbip_has_a0_[assign_num_left - 1] = IsAny<AssignSet>(result);
	affectsbip_has_a0_cache_[assign_num_left - 1] = true;
	if( !affectsbip_has_00_cache_ )
	{
		if( affectsbip_has_a0_[assign_num_left - 1] )
		{
			affectsbip_has_00_ = true;
			affectsbip_has_00_cache_ = true;
		}
		else if( IsAll<AssignSet>(affectsbip_has_a0_cache_) )
		{
			affectsbip_has_00_ = false;
			affectsbip_has_00_cache_ = true;
		}
	}
	return affectsbip_table_[assign_num_left - 1];
}

static bool FnComp (PathUnitEntry* lhs,  PathUnitEntry* rhs)
{
	//frontier
	if (lhs->frontier<rhs->frontier) return true;
	if (lhs->frontier>rhs->frontier) return false;
	//call_stack
	if (lhs->call_stack.size()<rhs->call_stack.size()) return true;
	if (lhs->call_stack.size()>rhs->call_stack.size()) return false;
	list<BlkIdx>::iterator call_it_l,call_it_r;
	call_it_r=rhs->call_stack.begin();
	for(call_it_l=lhs->call_stack.begin();call_it_l!=lhs->call_stack.end();call_it_l++)
	{
		if(*call_it_l<*call_it_r) return true;
		if(*call_it_l>*call_it_r) return false;
		if (call_it_r !=rhs->call_stack.end()) call_it_r++;
	}
	//while_entry
	if (lhs->while_entry.size()<rhs->while_entry.size()) return true;
	if (lhs->while_entry.size()>rhs->while_entry.size()) return false;
	list<BlkIdx>::iterator while_it_l,while_it_r;
	while_it_r=rhs->call_stack.begin();
	for(while_it_l=lhs->call_stack.begin();while_it_l!=lhs->call_stack.end();while_it_l++)
	{
		if(*while_it_l<*while_it_r) return true;
		if(*while_it_l>*while_it_r) return false;
		if (while_it_r !=rhs->call_stack.end()) while_it_r++;
	}
	//affects_var
	for(int i=0;i<lhs->affects_var.size();i++)
	{
		if(lhs->affects_var[i]<rhs->affects_var[i]) return true;
		if(lhs->affects_var[i]>rhs->affects_var[i]) return false;
	}
	return false;
}

AssignSet& AffectsBip::GetAffectsBipRightAdv(AssignNum assign_num_left)
{
	bool(*fn_pt)(PathUnitEntry*,PathUnitEntry*) = FnComp;
	set<PathUnitEntry*,bool(*)(PathUnitEntry*,PathUnitEntry*)> path_unit_set(fn_pt);
	stack<FrontierStackEntry*> call_path;
	VarIdx original_modifies = StmtTable::GetAssignTNode(assign_num_left)->child->value;
	AssignSet result(StmtTable::GetSizeAssign(), false);
	bool none_affected = false; bool affects_vars_changed = false; 
	int ComputeCallerRight_count = 0;
	//if cached, return result
	if( affectsbip_star_table_cache_[assign_num_left - 1] )
		return affectsbip_star_table_[assign_num_left - 1];

	//Traverse through current blknode
	bool affected = false;
	int modifies_var;
	VarSet affects_vars =Modifies::GetModifiesS(StmtTable::GetAssignTNode(assign_num_left)->stmt_num);  
	VarSet used_var,modifies_varset;
	BlkIdx blkidx = StmtTable::GetStmtBlkNode(StmtTable::GetAssignTNode(assign_num_left)->stmt_num)->blk_idx;
	for(int i=StmtTable::GetAssignTNode(assign_num_left)->stmt_num+1;i<=BlkTable::GetBlkNode(blkidx)->stmt_num_end;i++)
	{

		affected = false;
		modifies_varset =Modifies::GetModifiesS(i);  
		used_var = Uses::GetUsesS(i);
		for(int m=0; m<VarTable::GetSize(); m++)
		{
			if(modifies_varset[m]==true) {modifies_var = m+1; break;}
		}
		for (int a=0;a<VarTable::GetSize();a++) //loop affects_var
		{
			//used a affected variable
			if(affects_vars[a]==true  && used_var[a]==true)
			{
				result[StmtTable::GetStmtTNode(i)->value-1] = true;
				affects_vars[modifies_var-1] = true; 
				affected=true;
				break;
			}
		}
		if(!affected) {affects_vars[modifies_var-1]= false;}
	}


	BlkSet current_frontiers = BlkTable::GetNextBlkRight(StmtTable::GetStmtBlkNode(StmtTable::GetAssignTNode(assign_num_left)->stmt_num)->blk_idx);
	//push frontier blknode into stack_frontier.
	if (original_modifies != 0)
	{
		for( int i = 0; i < BlkTable::GetSize(); i++ )
		{
			if( current_frontiers[i])
			{
				FrontierStackEntry* p_frontier_stack_entry_new = new FrontierStackEntry();
				p_frontier_stack_entry_new->frontier=i+1;
				p_frontier_stack_entry_new->affects_vars.resize(VarTable::GetSize());
				p_frontier_stack_entry_new->affects_vars = affects_vars;
				call_path.push(p_frontier_stack_entry_new);
			}
		}
	}
	if (call_path.empty()&&original_modifies!=0)
	{
		//***
		FrontierStackEntry* p_frontier_stack_entry_new = new FrontierStackEntry();
		p_frontier_stack_entry_new->affects_vars.resize(VarTable::GetSize());
		p_frontier_stack_entry_new->affects_vars = affects_vars;
		ComputeCallerRight(call_path,StmtTable::GetProcIdx(StmtTable::GetAssignTNode(assign_num_left)->stmt_num), p_frontier_stack_entry_new);
	}

	while(!call_path.empty())
	{
		affects_vars_changed=false; 
		if (BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == ASSIGN_TYPE)	
		{
			UpdateAffectsVarsForAssignBlkNode(call_path.top()->affects_vars, call_path.top()->frontier, result);

			for (int i=0; i<VarTable::GetSize(); i++)
			{
				if(call_path.top()->affects_vars[i] == true) { break;}
				if(i==VarTable::GetSize()-1) {none_affected=true;}
			}

			//If no var is affected, stop the path
			if (none_affected)
			{
				none_affected=false;
				call_path.pop();
				//call_path.top()->affects_vars[original_modifies-1] = false;
			}
			else if (BlkTable::GetBlkNode(call_path.top()->frontier)->next_a != NULL)
			{
				//push new frontiers
				FrontierStackEntry* frontier_entry = call_path.top();
				call_path.pop();
				list<WhileEntry*> while_entry_list_temp;

				list<WhileEntry*>::iterator it;
				for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
				{ 
					WhileEntry* while_entry_temp= new WhileEntry() ;
					while_entry_temp->while_blknode=(*it)->while_blknode;
					while_entry_temp->affects_var=(*it)->affects_var;
					while_entry_list_temp.push_back(while_entry_temp);
				}
				AddFrontier(call_path, BlkTable::GetBlkNode(frontier_entry->frontier)->next_a->blk_idx,frontier_entry, while_entry_list_temp);
			}
			//end of proc
			else 
			{
				list<BlkIdx> call_stack_temp=call_path.top()->call_stack;
				if (!call_path.top()->call_stack.empty())
				{
					FrontierStackEntry* frontier_entry = call_path.top();
					while (!frontier_entry->call_stack.empty()&& BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a ==NULL)
					{
						call_stack_temp=call_path.top()->call_stack;
						frontier_entry->call_stack.pop_back();
					}
					frontier_entry->call_stack=call_path.top()->call_stack;	
					//modify call_stack and while_stack
					frontier_entry->while_entry=call_path.top()->while_entry;
					call_path.pop();
					if(!frontier_entry->call_stack.empty())
					{	
						list<WhileEntry*> while_entry_list_temp;
						list<WhileEntry*>::iterator it;
						for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
						{ 
							WhileEntry* while_entry_temp= new WhileEntry() ;
							while_entry_temp->while_blknode=(*it)->while_blknode;
							while_entry_temp->affects_var=(*it)->affects_var;
							while_entry_list_temp.push_back(while_entry_temp);
						}
						AddFrontier(call_path, BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a->blk_idx,frontier_entry,while_entry_list_temp);
						call_path.top()->call_stack.pop_back();}
					else{}
				}
				else{
					FrontierStackEntry* frontier_entry = call_path.top();
					ComputeCallerRight_count ++;
					call_path.pop();
					ComputeCallerRight(call_path,StmtTable::GetProcIdx(BlkTable::GetBlkNode(frontier_entry->frontier)->stmt_num_start), frontier_entry);
				}
			}

		}

		else if(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == WHILE_TYPE )
		{
			if (call_path.top()->while_entry.size() !=0)
			{
				for(int i=0;i<VarTable::GetSize();i++)
				{
					if(call_path.top()->affects_vars[i]==true&&call_path.top()->while_entry.back()->affects_var[i]==false) {affects_vars_changed = true; break;}
				}
			}

			if (call_path.top()->while_entry.size() ==0 || call_path.top()->while_entry.back()->while_blknode != BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx || affects_vars_changed == true)
			{

				if(!call_path.top()->while_entry.empty() && call_path.top()->while_entry.back()->while_blknode == BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx && affects_vars_changed==true) 
				{
					call_path.top()->while_entry.pop_back();
				}
				FrontierStackEntry* frontier_entry = call_path.top();
				//add next_a
				WhileEntry* while_entry=new WhileEntry();
				while_entry->affects_var=frontier_entry->affects_vars;
				while_entry->while_blknode = BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx;

				frontier_entry->while_entry.push_back(while_entry);
				call_path.pop();
				BlkIdx while_next_stmt_a = BlkTable::GetBlkNode(frontier_entry->frontier)->next_a->blk_idx;
				list<WhileEntry*> while_entry_list_temp;
				list<WhileEntry*>::iterator it;
				for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
				{ 
					WhileEntry* while_entry_temp= new WhileEntry() ;
					while_entry_temp->while_blknode=(*it)->while_blknode;
					while_entry_temp->affects_var=(*it)->affects_var;
					while_entry_list_temp.push_back(while_entry_temp);
				}
				AddFrontier(call_path, while_next_stmt_a,frontier_entry,while_entry_list_temp);
				//add path_unit into path_unit_set
				PathUnitEntry* path_unit=new PathUnitEntry();
				path_unit->call_stack=call_path.top()->call_stack;
				path_unit->frontier=call_path.top()->frontier;
				path_unit->affects_var=call_path.top()->affects_vars;
				for(it=call_path.top()->while_entry.begin();it!=call_path.top()->while_entry.end();it++)
				{
					path_unit->while_entry.push_back((*it)->while_blknode);
				}
				if(path_unit_set.count(path_unit)!=0) 
				{

					call_path.pop(); 
				}
				else
				{
					path_unit_set.insert(path_unit);
				}

				//add next_b
				if (BlkTable::GetBlkNode(frontier_entry->frontier)->next_b != NULL)
				{
					BlkIdx while_next_stmt_a = BlkTable::GetBlkNode(frontier_entry->frontier)->next_b->blk_idx;
					frontier_entry->while_entry.pop_back();
					list<WhileEntry*> while_entry_list_temp;
					list<WhileEntry*>::iterator it;
					for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
					{ 
						WhileEntry* while_entry_temp= new WhileEntry() ;
						while_entry_temp->while_blknode=(*it)->while_blknode;
						while_entry_temp->affects_var=(*it)->affects_var;
						while_entry_list_temp.push_back(while_entry_temp);
					}
					AddFrontier(call_path, while_next_stmt_a,frontier_entry,while_entry_list_temp);
					//add path_unit into path_unit_set
					PathUnitEntry* path_unit=new PathUnitEntry();
					path_unit->call_stack=call_path.top()->call_stack;
					path_unit->frontier=call_path.top()->frontier;
					path_unit->affects_var=call_path.top()->affects_vars;
					for(it=call_path.top()->while_entry.begin();it!=call_path.top()->while_entry.end();it++)
					{
						path_unit->while_entry.push_back((*it)->while_blknode);
					}

					if(path_unit_set.count(path_unit)!=0) 
					{

						call_path.pop();
					}
					else
					{
						path_unit_set.insert(path_unit);
					}
				}
				else
				{
					if(!frontier_entry->call_stack.empty())
					{
						while (!frontier_entry->call_stack.empty()&&BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a ==NULL)
						{
							frontier_entry->call_stack.pop_back();
						}
						if(!frontier_entry->call_stack.empty())
						{
							/*FrontierStackEntry* frontier_entry_b= new FrontierStackEntry();
							frontier_entry_b->while_entry=frontier_entry->while_entry;
							frontier_entry_b->affects_vars=frontier_entry->affects_vars;
							list<BlkIdx>::iterator list_it;
							for (list_it=frontier_entry->call_stack.begin();list_it!=frontier_entry->call_stack.end();list_it++)
							{
							frontier_entry_b->call_stack.push_back(*list_it);
							}*/
							//modify call_stack and while_stack
							//***
							frontier_entry->while_entry.pop_back();
							list<WhileEntry*> while_entry_list_temp;


							list<WhileEntry*>::iterator it;
							for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
							{ 
								WhileEntry* while_entry_temp= new WhileEntry() ;
								while_entry_temp->while_blknode=(*it)->while_blknode;
								while_entry_temp->affects_var=(*it)->affects_var;
								while_entry_list_temp.push_back(while_entry_temp);
							}
							if(BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a!=NULL)
							{AddFrontier(call_path,BlkTable::GetBlkNode(frontier_entry->call_stack.back())->next_a->blk_idx,frontier_entry,while_entry_list_temp);
							call_path.top()->call_stack.pop_back();
							//add path_unit into path_unit_set
							PathUnitEntry* path_unit=new PathUnitEntry();
							path_unit->call_stack=call_path.top()->call_stack;
							path_unit->frontier=call_path.top()->frontier;
							path_unit->affects_var=call_path.top()->affects_vars;
							for(it=call_path.top()->while_entry.begin();it!=call_path.top()->while_entry.end();it++)
							{
								path_unit->while_entry.push_back((*it)->while_blknode);
							}
							if(path_unit_set.count(path_unit)!=0) 
							{call_path.pop(); }
							else
							{
								path_unit_set.insert(path_unit);
							}
							}
							else
							{
								//ComputeCallerRight(call_path,StmtTable::GetProcIdx(BlkTable::GetBlkNode(frontier_entry->frontier)->stmt_num_start),frontier_entry);
								//***
							}
						}
					}
					else
					{
						ComputeCallerRight_count ++;
						//FrontierStackEntry* frontier_entry=call_path.top();
						ComputeCallerRight(call_path,StmtTable::GetProcIdx(BlkTable::GetBlkNode(frontier_entry->frontier)->stmt_num_start), frontier_entry);
						//add caller_proc into caller_proc_pathf
					}


				}
			}
			//X time reach a while statement. and var_affected is not changed
			else {
				call_path.pop();
			}	
		}

		else if(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_type == CALL_TYPE )
		{
			//real call next blkNode
			StmtNum call_stmt_next = ProcTable::GetStmtNumStart(StmtTable::GetStmtTNode(BlkTable::GetBlkNode(call_path.top()->frontier)->stmt_num_start)->value);
			BlkNode* call_blk_next = StmtTable::GetStmtBlkNode(ProcTable::GetStmtNumStart(StmtTable::GetStmtTNode(BlkTable::GetBlkNode(call_path.top()->frontier)->stmt_num_start)->value));

			//add new element into call_path
			FrontierStackEntry* p_frontier_stack_entry_new = new FrontierStackEntry();
			p_frontier_stack_entry_new->frontier=call_blk_next->blk_idx;
			p_frontier_stack_entry_new->call_stack=call_path.top()->call_stack;
			p_frontier_stack_entry_new->call_stack.push_back(BlkTable::GetBlkNode(call_path.top()->frontier)->blk_idx);
			p_frontier_stack_entry_new->while_entry=call_path.top()->while_entry;
			p_frontier_stack_entry_new->affects_vars = call_path.top()->affects_vars;
			call_path.pop();
			call_path.push(p_frontier_stack_entry_new);

			//add path_unit into path_unit_set
			PathUnitEntry* path_unit=new PathUnitEntry();
			path_unit->call_stack=call_path.top()->call_stack;
			path_unit->frontier=call_path.top()->frontier;
			path_unit->affects_var=call_path.top()->affects_vars;
			list<WhileEntry*>::iterator it;
			for(it=call_path.top()->while_entry.begin();it!=call_path.top()->while_entry.end();it++)
			{
				path_unit->while_entry.push_back((*it)->while_blknode);
			}
			if(path_unit_set.count(path_unit)!=0) 
			{
				call_path.pop();
			}
			else
			{
				path_unit_set.insert(path_unit);
			}
		}
		//If statement always has next_a
		else
		{
			//push new frontiers
			current_frontiers = BlkTable::GetNextBlkRight(call_path.top()->frontier);
			FrontierStackEntry* frontier_entry = call_path.top();
			call_path.pop();
			for( int i = 0; i < BlkTable::GetSize(); i++ )
			{
				if( current_frontiers[i] )
				{
					list<WhileEntry*> while_entry_list_temp;


					list<WhileEntry*>::iterator it;
					for (it=frontier_entry->while_entry.begin(); it!=frontier_entry->while_entry.end(); it++)
					{ 
						WhileEntry* while_entry_temp= new WhileEntry();
						while_entry_temp->while_blknode=(*it)->while_blknode;
						while_entry_temp->affects_var=(*it)->affects_var;
						while_entry_list_temp.push_back(while_entry_temp);
					}
					AddFrontier(call_path,i+1,frontier_entry,while_entry_list_temp);
				}
			}

		}
		//if stack is empty, add all other procedure.


	}
	affectsbip_star_table_[assign_num_left - 1] = result;
	affectsbip_star_table_cache_[assign_num_left - 1] = true;
	return affectsbip_star_table_[assign_num_left - 1];
}

AssignSet& AffectsBip::GetAffectsBipLeft(AssignNum assign_num_right)
{
	AssignSet result(StmtTable::GetSizeAssign(), false);
	for(int i=1;i<=StmtTable::GetSizeAssign();i++)
	{
		result[i-1]=GetAffectsBipRight(StmtTable::GetStmtTNode(i)->stmt_num)[assign_num_right-1];
	}
	affectsbip_table_t_[assign_num_right - 1] = result;
	affectsbip_has_0a_[assign_num_right - 1] = IsAny<AssignSet>(result);
	affectsbip_has_0a_cache_[assign_num_right - 1] = true;
	if( !affectsbip_has_00_cache_ )
	{
		if( affectsbip_has_0a_[assign_num_right - 1] )
		{
			affectsbip_has_00_ = true;
			affectsbip_has_00_cache_ = true;
		}
		else if( IsAll<AssignSet>(affectsbip_has_0a_cache_) )
		{
			affectsbip_has_00_ = false;
			affectsbip_has_00_cache_ = true;
		}
	}
	return affectsbip_table_[assign_num_right - 1];
}

bool AffectsBip::IsAffectsBip(StmtNum assign_num_left, StmtNum assign_num_right)
{

	if( assign_num_left > StmtTable::GetSize() ||
		assign_num_right > StmtTable::GetSize() ||
		(assign_num_left != 0 && StmtTable::GetStmtTNode(assign_num_left)->type != ASSIGN_TYPE) ||
		(assign_num_right != 0 && StmtTable::GetStmtTNode(assign_num_right)->type != ASSIGN_TYPE) )
		return false;

	if( assign_num_left != 0 && assign_num_right != 0 &&
		!NextBip::IsNextBipAdv(assign_num_left, assign_num_right) )
		return false;

	if( assign_num_left == 0 && assign_num_right == 0 )
	{
		for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
		{
			if( affectsbip_has_00_cache_ ) break;
			GetAffectsBipRight(i+1);
		}
		return affectsbip_has_00_;
	}

	if( assign_num_left == 0 )
	{
		if( affectsbip_has_0a_cache_[StmtTable::GetStmtTNode(assign_num_right)->value - 1] )
			return affectsbip_has_0a_[StmtTable::GetStmtTNode(assign_num_right)->value - 1];
		GetAffectsBipLeft(StmtTable::GetStmtTNode(assign_num_right)->value);
		return affectsbip_has_0a_[StmtTable::GetStmtTNode(assign_num_right)->value - 1];
	}

	if( assign_num_right == 0 )
	{
		if( affectsbip_has_a0_cache_[StmtTable::GetStmtTNode(assign_num_left)->value - 1] )
			return affectsbip_has_a0_[StmtTable::GetStmtTNode(assign_num_left)->value - 1];
		GetAffectsBipRight(StmtTable::GetStmtTNode(assign_num_left)->value);
		return affectsbip_has_a0_[StmtTable::GetStmtTNode(assign_num_left)->value - 1];
	}

	if( affectsbip_has_a0_cache_[StmtTable::GetStmtTNode(assign_num_left)->value - 1] )
		return affectsbip_table_[StmtTable::GetStmtTNode(assign_num_left)->value - 1][StmtTable::GetStmtTNode(assign_num_right)->value - 1];
	if( affectsbip_has_0a_cache_[StmtTable::GetStmtTNode(assign_num_right)->value - 1] )
		return affectsbip_table_t_[StmtTable::GetStmtTNode(assign_num_right)->value - 1][StmtTable::GetStmtTNode(assign_num_left)->value - 1];

	AssignSet& result = GetAffectsBipRight(StmtTable::GetStmtTNode(assign_num_left)->value);
	return result[StmtTable::GetStmtTNode(assign_num_right)->value - 1];

}

bool AffectsBip::IsAffectsBipAdv(StmtNum assign_num_left, StmtNum assign_num_right)
{
	if( assign_num_left > StmtTable::GetSize() ||
		assign_num_right > StmtTable::GetSize() ||
		(assign_num_left != 0 && StmtTable::GetStmtTNode(assign_num_left)->type != ASSIGN_TYPE) ||
		(assign_num_right != 0 && StmtTable::GetStmtTNode(assign_num_right)->type != ASSIGN_TYPE) )
		return false;

	if( assign_num_left != 0 && assign_num_right != 0 &&
		//Need change to NextBIp
		!NextBip::IsNextBipAdv(assign_num_left, assign_num_right) )
		return false;

	if( assign_num_left == 0 && assign_num_right == 0 )
	{
		for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
		{
			if( affectsbip_has_00_cache_ ) break;
			GetAffectsBipRight(i+1);
		}
		return affectsbip_has_00_;
	}

	if( assign_num_left == 0 )
	{
		if( affectsbip_has_0a_cache_[StmtTable::GetStmtTNode(assign_num_right)->value - 1] )
			return affectsbip_has_0a_[StmtTable::GetStmtTNode(assign_num_right)->value - 1];
		GetAffectsBipLeft(StmtTable::GetStmtTNode(assign_num_right)->value);
		return affectsbip_has_0a_[StmtTable::GetStmtTNode(assign_num_right)->value - 1];
	}

	if( assign_num_right == 0 )
	{
		if( affectsbip_has_a0_cache_[StmtTable::GetStmtTNode(assign_num_left)->value - 1] )
			return affectsbip_has_a0_[StmtTable::GetStmtTNode(assign_num_left)->value - 1];
		GetAffectsBipRight(StmtTable::GetStmtTNode(assign_num_left)->value);
		return affectsbip_has_a0_[StmtTable::GetStmtTNode(assign_num_left)->value - 1];
	}

	if( affectsbip_star_table_cache_[StmtTable::GetStmtTNode(assign_num_left)->value - 1] )
		return affectsbip_star_table_[StmtTable::GetStmtTNode(assign_num_left)->value - 1][StmtTable::GetStmtTNode(assign_num_right)->value - 1];

	AssignSet& result = GetAffectsBipRightAdv(StmtTable::GetStmtTNode(assign_num_left)->value);
	return result[StmtTable::GetStmtTNode(assign_num_right)->value - 1];

}

string AffectsBip::ToString(){
	stringstream ss;
	ss << "AffectsBip : [" << affectsbip_has_00_cache_ << "] : " << affectsbip_has_00_ << endl;

	for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
	{
		ss << StmtTable::GetAssignTNode(i+1)->stmt_num << " : [" << affectsbip_has_a0_cache_[i] << "]";
		if( affectsbip_has_a0_cache_[i] )
		{
			for( int j = 0; j < StmtTable::GetSizeAssign(); j++ )
				ss << " " << affectsbip_table_[i][j];
		}
		ss << endl;
	}

	ss<< endl << endl;

	for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
	{
		ss << StmtTable::GetAssignTNode(i+1)->stmt_num << " : [" << affectsbip_has_0a_cache_[i] << "]";
		if( affectsbip_has_0a_cache_[i] )
		{
			for( int j = 0; j < StmtTable::GetSizeAssign(); j++ )
				ss << " " << affectsbip_table_t_[i][j];
		}
		ss << endl;
	}

	ss<< endl << endl;

	for( int i = 0; i < StmtTable::GetSizeAssign(); i++ )
	{
		ss << StmtTable::GetAssignTNode(i+1)->stmt_num << " : ";
		if( affectsbip_star_table_cache_[i] )
		{for( int j = 0; j < StmtTable::GetSizeAssign(); j++ )
		{

			ss << " " << affectsbip_star_table_[i][j];

		}}
		else
		{ss << " _";}
		ss << endl;
	}

	return ss.str();
}
